public class MaxSubarraySum {  
    public static int maxSubArraySum(int[] a) {  
        int maxSoFar = a[0];  
        int currMax = a[0];  
  
        for (int i = 1; i < a.length; i++) {  
            currMax = Math.max(a[i], currMax + a[i]);  
            maxSoFar = Math.max(maxSoFar, currMax);  
        }  
  
        return maxSoFar;  
    }  
  
    public static void main(String[] args) {  
        int[] arr = {1, -2, 3, 5, -1};  
        System.out.println("Maximum contiguous sum is " + maxSubArraySum(arr));  
  
        int[] arr2 = {1, -2, 3, -8, 5, 1};  
        System.out.println("Maximum contiguous sum is " + maxSubArraySum(arr2));  
  
        int[] arr3 = {1, -2, 3, -2, 5, 1};  
        System.out.println("Maximum contiguous sum is " + maxSubArraySum(arr3));  
    }  
}